package algorithm.array;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个数组 nums和一个整型变量K，找出数组中是否存在两个索引 i，j  满足  nums[i] == nums[j] ,并且 abs(i - j) <= k
 *
 * Input: nums = [1,2,3,1], k = 3
 * Output: true
 *
 * Input: nums = [1,2,3,1,2,3], k = 2
 * Output: false
 */
public class ContainsNearbyDuplicate {

    public static void main(String[] args) {

        int [] nums = {1,2,3,1};
        int [] nums1 = {1,2,3,1,2,3}; //2
        int [] nums2 = {1,0,1,1}; //1
        System.out.println(containsNearbyDuplicate(nums2, 1));
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {


        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
